package com.cuz.daileetcode;

public class Day43 {


    /***
     * 有N(N>=0)个草 和两种绝顶聪明的牛
     * 依次吃 4的x次方草 (0=<x 且 4的x次方要小于当前剩余的草量）
     *
     * 两个·牛叫先手牛（指先手吃草）和后手牛，如果先手牛吃完最后一份草
     * 那么先手牛获胜 反之后手牛获胜（也就是那头牛先没有草吃 那么另外一只获胜）
     *
     * 先手牛赢返回true 反之返回false
     */
    public static class CattleEatGrass {

        static boolean solution1(int n) {
            if (n < 5) {
                // 0棵草 先手牛直接没有草吃
                //2 棵草 先手1棵 后手1棵，最后先手牛没有草吃
                if (n == 0 || n == 2) {
                    return false;
                } else {
                    return true;
                }
            }
            //当前先手牛 吃草量
            int curEatNum = 1;
            while (curEatNum <= n) {
                //如果 先手牛吃完后，后手牛赢了 那么返回先手牛赢
                //怎么理解
                //先手牛A吃完后 先手牛变成接下来过程中的后手牛了，如果子过程返回了先手牛
                //那么说明父过程中的先手牛输了，但是它是一只绝顶聪明的牛呀
                // ，自己输了之和会继续尝试其他的4的x次幂。所以只有自己赢的时候返回true
                if (!solution1(n - curEatNum)) {
                    return true;
                }
                //如果越界 那么说明再怎么尝试也无济于事了 那么返回false 先手牛必输
                if (curEatNum > n / 4) {
                    return false;
                }
                //反之 这种吃法先手牛没办法赢，那么多吃一点看看自己能不能赢
                curEatNum *= 4;
            }
            return false;
        }

        public static void main(String[] args) {
            for (int n = 0; n < 100; n++) {
                System.out.println(n + "===>" + (solution1(n) ? "先手" : "后手"));
            }
        }

        static boolean solution2(int n) {
            return n % 5 != 0 && n % 5 != 2;
        }
    }

    /**
     * 见笔记 【DaiLeetCode43牛吃草问题（博弈论，打表法），染色块问题（预处理数组法）】
     */
    static class ColorAlter {
        public static void main(String[] args) {
            System.out.println(solution1("RGRGR"));
        }

        static int solution1(String colorSeq) {
            char[] colorChars = colorSeq.toCharArray();
            int len = colorChars.length;
            //记录从 0到index 存在多少个G
            int[] gMemory = new int[len];
            //记录从 index到len-1 存在多少个R
            int[] rMemory = new int[len];
            //"RGRGR"
            for (int index = 0; index < len; index++) {
                if (index == 0 ) {
                    if ( colorChars[index] == 'G'){
                        gMemory[0] = 1;
                    }

                } else {
                    gMemory[index] = gMemory[index - 1];
                    if (colorChars[index] == 'G') {
                        gMemory[index] += 1;
                    }
                }
            }
            for (int index = len - 1; index >= 0; index--) {
                if (index == len - 1) {
                    if (colorChars[index] == 'R'){
                        rMemory[0] = 1;
                    }
                }else {
                    rMemory[index] = rMemory[index + 1];
                    if (colorChars[index] == 'R') {
                        rMemory[index] += 1;
                    }
                }
            }
            int res = Integer.MAX_VALUE;
            for (int index = 0; index < len; index++) {
                res = Math.min(res, gMemory[index] + rMemory[index]);
            }
            return res;
        }
    }
}
